package com.zk.algorithm.dynamicprogramming;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.BianChengZhiMei;
import com.zk.algorithm.annotation.LeetCode;

import java.util.Arrays;

/**
 * 最长递增子序列
 *
 * 1,-1,2,-3,4,-5,6,-7 => 1,2,4,6
 *
 * @author zk
 */
@BianChengZhiMei("2.16")
@LeetCode("300")
public class LongestIncreasingSubsequence {

    // 1, -1, 2, -3, 4, -5, 6, -7
    // ↑
    // 1
    //
    //    ↑
    //   -1
    //
    //        ↑
    //  (1,2) 或 (-1,2) 2 前面是 1 还是 -1 对求出后面的递增序列没有直接影响
    //
    // 假设前 i 个元素，最长递增子序列为长度为LIS[i]，那么
    // LIS[i + 1] = max{1, LIS[k] + 1}, array[i + 1] > array[k], for any k <= i
    //
    // O(N^2 + N) = O(N^2)
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] lis = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            // i 元素本身至少构成一个长度为 1 的最长递增子序列
            lis[i] = 1;

            // 对于任何一个 k
            for (int k = 0; k < i; k++) {
                if (nums[i] > nums[k] && lis[k] + 1 > lis[i]) {
                    lis[i] = lis[k] + 1;
                }
            }

        }

        // 找出数组中的最大值
        return Arrays.stream(lis).max().getAsInt();
    }

    // ==============================
    // ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
    // 优化
    //
    // 假设前面最长的递增子序列长度为 2，构成序列为:
    // (1, 2) 或 (-3, -1)
    //
    // 那么当下一个元素为 0，则需要确定 (1, 2, 0) 构不成，(-3, -1, 0) 可以构成，
    // 即需要跟踪构成递增子序列长度为 2 的两个序列的最大元素的最小的值 (-1)
    // (1, 2)
    //     ↑
    //
    // (-3, -1)
    //      ↑
    // ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
    // ==============================
    public int lengthOfLIS2(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }

        int[] maxV = new int[array.length + 1];
        maxV[0] = Integer.MIN_VALUE;
        maxV[1] = array[0]; // 长度为 1 的递增子序列的最小值

        int[] lis = new int[array.length];
        Arrays.fill(lis, 1);

        int nMaxLIS = 1;
        for (int i = 1; i < array.length; i++) {

            int j;
            for (j = nMaxLIS; j >= 0; j--) {
                if (array[i] > maxV[j]) {
                    lis[i] = j + 1;
                    break;
                }
            }

            // 10, 9, 2, 5, 3, 7, 101, 18
            //    ↑ (长度为 1 更新, 10 => 9, 9 更小)
            //        ↑ (长度为 1 更新, 2 => 9, 2 更小)
            //          ↑ (追加)
            //             ↑ (长度为 2 更新, 3 => 5, 3 更小)
            //                ↑ (追加)
            //                    ↑ (追加)
            //                         ↑ (长度为 4 更新, 18 => 101, 18 更小)
            //
            // 10, 9, 2, 5, 3, 7, 101, 18
            //     ↑
            //   9 > 10 吗
            //   9 > Integer.MIN_VALUE 吗
            //
            //   maxV: [Integer.MIN_VALUE, 10]
            //                 ↑
            //                 j
            //   maxV: [Integer.MIN_VALUE, 9]
            //
            //        ↑
            //     2 > 10 吗
            //     2 > Integer.MIN_VALUE 吗
            //
            //   maxV: [Integer.MIN_VALUE, 9]
            //                 ↑
            //                 j
            //   maxV: [Integer.MIN_VALUE, 2]
            //
            //             ↑
            //           3 > 5 吗
            //           3 > 2 吗
            //
            //   maxV: [Integer.MIN_VALUE, 2, 5]
            //                             ↑
            //                             j
            //   maxV: [Integer.MIN_VALUE, 2, 3]
            //
            //                           ↑
            //                        18 > 101 吗
            //                        18 > 7 吗
            //
            //   maxV: [Integer.MIN_VALUE, 2, 3, 7, 101]
            //                                   ↑
            //                                   j
            //   maxV: [Integer.MIN_VALUE, 2, 3, 7, 18]

            // 追加新的元素
            if (lis[i] > nMaxLIS) {
                nMaxLIS = lis[i];
                maxV[nMaxLIS] = array[i];
            } else if (maxV[j] < array[i] && array[i] < maxV[j + 1]) {
                // 更新的旧的值
                //
                // [...j..j+1]
                //         ↑
                //
                // [...j..i]
                //        ↑
                //
                maxV[j + 1] = array[i];
            }

        }

        return nMaxLIS;
    }

    // ==========================================
    // 网友的
    // https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/810/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation
    //
    // nums = [4,5,6,3]
    // len = 1   :      [4], [5], [6], [3]   => tails[0] = 3。解释：长度为 1 的递增序列有 4,5,6,3，但是这几个序列末尾最小的是 3
    // len = 2   :      [4, 5], [5, 6]       => tails[1] = 5。解释：长度为 2 的递增序列有 [4,5]、[5,6]，但是这几个序列末尾最小的是 5
    // len = 3   :      [4, 5, 6]            => tails[2] = 6。解释：长度为 3 的递增序列有 [4,5,6]，但是序列末尾最小的是 6
    //
    // tail 数组是一个递增有序数组，因此可以二叉搜索
    // ==========================================
    public int lengthOfLIS3(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;

        for (int x : nums) {
            // 1. 大于所有 tail，那么 size++，追加这个数字到 tail
            // 2. tails[i-1] < x <= tails[i]，那么更新 tails[i]
            int i = 0, j = size;
            while (i != j) {
                int m = (i + j) / 2;
                if (tails[m] < x)
                    i = m + 1;
                else
                    j = m;
            }

            tails[i] = x;
            if (i == size) ++size;
        }
        return size;
    }

    public static void main(String...args) {
        Utils.println(new LongestIncreasingSubsequence().lengthOfLIS2(new int[]{
                10,9,2,5,3,7,101,18
        }));
    }

}
